package com.ma.dp.a01;

import java.util.Arrays;

/**
 * @ClassName Solution931
 * @Author: mayongqiang
 * @DATE 2022/4/2 10:56
 * @Description:
 */
public class Solution931 {
    /*给你一个 n x n 的 方形 整数数组matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
    下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。
    在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
    具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1)*/
    public static void main(String[] args) {

    }

    private static int[][] memo;

    public static int minFallingPathSum(int[][] matrix) {
        // 1、定义dp，明确其意义  dp[i][j] 表示从dp[0][0]到dp[i][j]的最小下降路径和
        int n = matrix.length;
        int res = Integer.MIN_VALUE;
        memo = new int[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], 66666);
        }

        // 终点一定在最后一行的某一列·
        for (int j = 0; j < n; j++) {
            res = Math.min(res, dp(matrix, n - 1, j));
        }
        return res;
    }


    private static int dp(int[][] matrix, int i, int j) {
        //边界处理
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) {
            return 99999;
        }

        // base case
        if (i == 0) {
            return matrix[i][j];
        }
        if (memo[i][j] != 66666) {
            return memo[i][j];
        }

        // 2、状态转移        dp[i][j] = Math.min( dp[i-1][j-1] , dp[i-1][j] , dp[i-1][j+1] )   + matrix[i][j]
        return memo[i][j] = matrix[i][j] + min(
                dp(matrix, i - 1, j - 1),
                dp(matrix, i - 1, j),
                dp(matrix, i - 1, j + 1)
        );

    }

    private static int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}
